{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Groups of Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #union-find #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #并查集 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: groupStrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串分组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从&nbsp;<strong>0&nbsp;</strong>开始的字符串数组&nbsp;<code>words</code>&nbsp;。每个字符串都只包含 <strong>小写英文字母</strong>&nbsp;。<code>words</code>&nbsp;中任意一个子串中，每个字母都至多只出现一次。</p>\n",
    "\n",
    "<p>如果通过以下操作之一，我们可以从 <code>s1</code>&nbsp;的字母集合得到 <code>s2</code>&nbsp;的字母集合，那么我们称这两个字符串为 <strong>关联的</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>往&nbsp;<code>s1</code>&nbsp;的字母集合中添加一个字母。</li>\n",
    "\t<li>从&nbsp;<code>s1</code>&nbsp;的字母集合中删去一个字母。</li>\n",
    "\t<li>将 <code>s1</code>&nbsp;中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>数组&nbsp;<code>words</code>&nbsp;可以分为一个或者多个无交集的 <strong>组</strong>&nbsp;。如果一个字符串与另一个字符串关联，那么它们应当属于同一个组。</p>\n",
    "\n",
    "<p>注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。</p>\n",
    "\n",
    "<p>请你返回一个长度为 <code>2</code>&nbsp;的数组&nbsp;<code>ans</code>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>ans[0]</code>&nbsp;是&nbsp;<code>words</code>&nbsp;分组后的&nbsp;<strong>总组数</strong>&nbsp;。</li>\n",
    "\t<li><code>ans[1]</code>&nbsp;是字符串数目最多的组所包含的字符串数目。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"a\",\"b\",\"ab\",\"cde\"]\n",
    "<b>输出：</b>[2,3]\n",
    "<b>解释：</b>\n",
    "- words[0] 可以得到 words[1] （将 'a' 替换为 'b'）和 words[2] （添加 'b'）。所以 words[0] 与 words[1] 和 words[2] 关联。\n",
    "- words[1] 可以得到 words[0] （将 'b' 替换为 'a'）和 words[2] （添加 'a'）。所以 words[1] 与 words[0] 和 words[2] 关联。\n",
    "- words[2] 可以得到 words[0] （删去 'b'）和 words[1] （删去 'a'）。所以 words[2] 与 words[0] 和 words[1] 关联。\n",
    "- words[3] 与 words 中其他字符串都不关联。\n",
    "所以，words 可以分成 2 个组 [\"a\",\"b\",\"ab\"] 和 [\"cde\"] 。最大的组大小为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"a\",\"ab\",\"abc\"]\n",
    "<b>输出：</b>[1,3]\n",
    "<strong>解释：</strong>\n",
    "- words[0] 与 words[1] 关联。\n",
    "- words[1] 与 words[0] 和 words[2] 关联。\n",
    "- words[2] 与 words[1] 关联。\n",
    "由于所有字符串与其他字符串都关联，所以它们全部在同一个组内。\n",
    "所以最大的组大小为 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 26</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li><code>words[i]</code> 中每个字母最多只出现一次。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [groups-of-strings](https://leetcode.cn/problems/groups-of-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [groups-of-strings](https://leetcode.cn/problems/groups-of-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"a\",\"b\",\"ab\",\"cde\"]', '[\"a\",\"ab\",\"abc\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def get_hash(string):\n",
    "            key = []\n",
    "            for a, b in zip(string, string[1:]):\n",
    "                key.append(chr((ord(b) - ord(a)) % 26 + ord(\"a\")))\n",
    "            return \"\".join(key)\n",
    "        groups = defaultdict(list)\n",
    "        for string in strings:\n",
    "            hash_key = get_hash(string)\n",
    "            print(hash_key)\n",
    "            groups[hash_key].append(string)\n",
    "        return list(groups.values())\n",
    "        # samelen_strings = defaultdict(list)\n",
    "        # for i in strings:\n",
    "        #     if len(i) == 1:\n",
    "        #         diff = 0\n",
    "        #         samelen_strings[(len(i), diff)].append(i)\n",
    "        #     elif len(i) == 2:\n",
    "        #         diff = ord(i[1]) - ord(i[0])\n",
    "        #         if diff < 0:\n",
    "        #             diff += 26\n",
    "        #         samelen_strings[(len(i), diff)].append(i)\n",
    "        #     else:\n",
    "        #         diff = ord(i[1]) - ord(i[0])\n",
    "        #         same_len = True\n",
    "        #         for j in range(2, len(i)):\n",
    "        #             temp = ord(i[j]) - ord(i[j - 1])\n",
    "                    \n",
    "        #             if temp < 0:\n",
    "        #                 temp += 26\n",
    "        #             if diff != temp:\n",
    "        #                 same_len = False\n",
    "        #                 break\n",
    "        #         if same_len == True:\n",
    "        #             samelen_strings[(len(i), diff)].append(i)\n",
    "        #         else:\n",
    "        #             samelen_strings[(-1, -1)].append(i)\n",
    "\n",
    "        # ans = []\n",
    "        \n",
    "        # for i in samelen_strings.keys():\n",
    "        #     if i != (-1, -1):\n",
    "        #         ans.append(samelen_strings[i])\n",
    "        #     else:\n",
    "               \n",
    "        #         for j in samelen_strings[i]:\n",
    "               \n",
    "        #             ans.append([j])\n",
    "\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def word_to_number(self, word):\n",
    "        res = ''\n",
    "        if len(word) == 1:\n",
    "            return ''\n",
    "        for i in range(len(word) - 1):\n",
    "            num = (ord(word[i + 1]) - ord(word[i]))%26\n",
    "            res += ',' + str(num)\n",
    "        return res\n",
    "\n",
    "    def groupStrings(self, strings: list[str]) -> list[list[str]]:\n",
    "        group_dict = defaultdict(list)\n",
    "        for word in strings:\n",
    "            group_dict[self.word_to_number(word)].append(word)\n",
    "        return list(group_dict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        check_dic = defaultdict(list)\n",
    "        for word in strings:\n",
    "            k = ''\n",
    "            for i in range(len(word) - 1):\n",
    "                res = (ord(word[i + 1]) - ord(word[i])) % 26\n",
    "                k += 'h' + str(res)\n",
    "            check_dic[k].append(word)\n",
    "        return list(check_dic.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        mp = defaultdict(list)\n",
    "        for s in strings:\n",
    "            k = []\n",
    "            for c in s:\n",
    "                k.append((ord(c) - ord(s[0])) % 26)\n",
    "            mp[tuple(k)].append(s)\n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        for s in strings:\n",
    "            key = []\n",
    "            start = s[0]\n",
    "            for i in range(1, len(s)):\n",
    "                key.append((ord(s[i]) - ord(start)) % 26)\n",
    "            str_key = \"#\".join(map(str, key))\n",
    "            dic[str_key].append(s)\n",
    "        \n",
    "        return [val for val in dic.values()]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        mp = {}\n",
    "        def tup(s: str) -> Optional[Tuple]:\n",
    "            lst = [ord(h)-ord(q)  if ord(h)-ord(q)>0 else ord(h)-ord(q)+26 for q,h in zip(s[:-1],s[1:])]\n",
    "            res,cnt = 0,26\n",
    "            for item in lst:\n",
    "                res+=item*cnt\n",
    "                cnt*=26\n",
    "            return res\n",
    "        res = []\n",
    "        for s in strings:\n",
    "            has = tup(s)\n",
    "            if has not in mp:\n",
    "                mp[has] = len(res)\n",
    "                res.append([s])\n",
    "            else:\n",
    "                res[mp[has]].append(s)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d = defaultdict(list)\n",
    "        for s in strings:\n",
    "            root = ''.join([chr((ord(c) - ord(s[0]) + 26) % 26 + ord('a')) for c in s])\n",
    "            d[root].append(s)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        stringMapping = {}\n",
    "\n",
    "        for string in strings:\n",
    "            offset = []\n",
    "            for letter in string:\n",
    "                curOffset = ord(letter) - ord(string[0])\n",
    "                if curOffset < 0:\n",
    "                    curOffset += 26\n",
    "                offset.append(curOffset)\n",
    "            offset = tuple(offset)\n",
    "            if offset in stringMapping:\n",
    "                stringMapping[offset].append(string)\n",
    "            else:\n",
    "                stringMapping[offset] = [string]\n",
    "        \n",
    "        \n",
    "        return list(stringMapping.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d =defaultdict(list)\n",
    "        for s in strings:\n",
    "            #  将 移位后相等的字符串 通过一种方式得到\n",
    "    \n",
    "            if s[0] == 'a':\n",
    "                d[s].append(s)\n",
    "            else:    \n",
    "                tmp = list(s)                       \n",
    "                for i in range(len(s)):\n",
    "                    # 对于每个单词，例如abc,转换成 012, 即 word-word[0] 对于每个字母。 然后把012放入字典，后面查找就行\n",
    "                    tmp[i] = chr( (ord(tmp[i]) - ord(s[0]) + 26) % 26 + ord('a') )\n",
    "                tmp = ''.join(tmp)\n",
    "                d[tmp].append(s)\n",
    "        return [v for i ,v in d.items()]\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        check = collections.defaultdict(list)\n",
    "\n",
    "        len1 = []\n",
    "        for s0 in strings:\n",
    "            if len(s0)==1:\n",
    "                len1.append(s0)\n",
    "                continue\n",
    "            found = False\n",
    "            for key in check:\n",
    "                if len(key)!=len(s0):\n",
    "                    continue \n",
    "                equal = True\n",
    "                for i in range(1,len(s0)):\n",
    "                    if (ord(s0[i])-ord(key[i]))%26 !=(ord(s0[i-1])-ord(key[i-1]))%26:\n",
    "                        equal = False\n",
    "                        break\n",
    "                if equal:\n",
    "                    check[key].append(s0)\n",
    "                    found = True\n",
    "                    break\n",
    "            if not found:\n",
    "                check[s0] = []\n",
    "        \n",
    "        ans = []\n",
    "        if len1:\n",
    "            ans.append(len1)\n",
    "        for key in check:\n",
    "            ans.append([key]+check[key])\n",
    "        return ans \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hashCounter(s) -> str:\n",
    "            k = \"\"\n",
    "            offset = ord(s[0]) - ord(\"a\")\n",
    "            for c in s:\n",
    "                k += chr(ord(\"a\") + (ord(c) - ord(\"a\") - offset) % 26)\n",
    "            return k\n",
    "\n",
    "        ans = defaultdict(list)\n",
    "        for s in strings:\n",
    "            ans[hashCounter(s)].append(s)\n",
    "        return list(ans.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def getGroup(string):\n",
    "            array = []\n",
    "            length = len(string)\n",
    "            for i in range(1,length):\n",
    "                diff = ord(string[i])-ord(string[i-1])\n",
    "                if diff < 0:\n",
    "                    diff += 26\n",
    "                array.append(diff)\n",
    "            return str(array)\n",
    "        groupMap = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            group = getGroup(s)\n",
    "            groupMap[group].append(s)\n",
    "        return list(groupMap.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        def order(x):\n",
    "            if x < 0:\n",
    "                return x + 26\n",
    "            return x\n",
    "\n",
    "        for s in strings:\n",
    "            l = len(s)\n",
    "            d = [str(order(ord(s[i]) - ord(s[i+1]))) for i in range(l-1)]\n",
    "            key = str(l) + str('|') + ''.join(d)\n",
    "            dic[key].append(s)\n",
    "\n",
    "        return [dic[x] for x in dic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d = defaultdict(list)\n",
    "        for w in strings:\n",
    "            t = '0'\n",
    "            for i in range(1,len(w)):\n",
    "                ti = ord(w[i])\n",
    "                if w[i]<w[0]:\n",
    "                    t += f',{ti-ord(w[0])+26}'\n",
    "                else:\n",
    "                    t += f',{ti-ord(w[0])}'\n",
    "            d[t].append(w)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def key_helper(string):\n",
    "            povit=string[0]\n",
    "            key=''\n",
    "            for char in string:\n",
    "                key+=str((ord(char)-ord(povit))%26)\n",
    "                key+=\" \"\n",
    "            return key\n",
    "        \n",
    "        hash_dict={}\n",
    "\n",
    "        for item in strings:\n",
    "            hash_key=key_helper(item)\n",
    "\n",
    "            if hash_key not in hash_dict:\n",
    "                hash_dict[hash_key]=[]\n",
    "            hash_dict[hash_key].append(item)\n",
    "        \n",
    "        res=[]\n",
    "\n",
    "        for key,val in hash_dict.items():\n",
    "            res.append(val)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        counter = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            temp = list(s)\n",
    "            temp = [str((ord(i)- ord(temp[0])) % 26) for i in temp]\n",
    "            temp = '*'.join(temp)\n",
    "            counter[temp].append(s)\n",
    "        return list(counter.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        hashmap={}\n",
    "        for i in strings:\n",
    "            lis=[]\n",
    "            for j in i:\n",
    "                change=chr(ord('a')+(ord(j)-ord(i[0])+26)%26)\n",
    "                lis.append(change)\n",
    "            str_change=''.join(lis)\n",
    "            hashmap[str_change]=hashmap.get(str_change,[])\n",
    "            hashmap[str_change].append(i)\n",
    "        return list(hashmap.values())\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d =defaultdict(list)\n",
    "        for s in strings:\n",
    "            # s_ = \"\".join(sorted(i))  # 将 移位后相等的字符串 通过一种方式得到\n",
    "            \n",
    "            if s[0] == 'a':\n",
    "                d[s].append(s)\n",
    "            else:    \n",
    "                tmp = list(s)                       #转化成一种模式 从'a****'\n",
    "                for i in range(len(s)):\n",
    "                    tmp[i] = chr( (ord(tmp[i]) - ord(s[0]) + 26) % 26 + ord('a') )\n",
    "                tmp = ''.join(tmp)\n",
    "                d[tmp].append(s)\n",
    "\n",
    "         \n",
    "        return [v for i ,v in d.items()]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hashSeq(s: str) -> int:\n",
    "            hs = ''\n",
    "            for i in range(1, len(s)):\n",
    "                diff = (ord(s[i]) - ord(s[i-1]) + 26) % 26\n",
    "                if diff < 10:  \n",
    "                    hs += \"0\" + str(diff)  \n",
    "                else:\n",
    "                    hs += str(diff)\n",
    "            return hs\n",
    "\n",
    "        arr = dict()\n",
    "        for s in strings:\n",
    "            hash = hashSeq(s)\n",
    "            li = arr.get(hash, list())\n",
    "            li.append(s)\n",
    "            arr[hash] = li\n",
    "\n",
    "        return list(arr.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hash(word):\n",
    "            # 相当于把所有单词还原到以a打头再重新算\n",
    "            ret = 0\n",
    "            base = ord(word[0]) - ord('a')\n",
    "            for c in word:\n",
    "                ret = ret * 26 + (ord(c) - base + 26) % 26\n",
    "            return ret\n",
    "\n",
    "        d = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            d[hash(word)].append(word)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        # maxlen = max([len(s) for s in strings])\n",
    "        # strings_new = [[s for s in strings if len(s) == i] for i in range(1, maxlen+1)]\n",
    "        # r = []\n",
    "        # # print()\n",
    "        # for s in strings_new:\n",
    "        #     # print(len(s),s)\n",
    "        #     if len(s[0]) == 1 or len(s) == 1:\n",
    "        #         r.append(s)\n",
    "        # return r\n",
    "        #有思路但没实现\n",
    "        mp = defaultdict(list)\n",
    "        for s in strings:\n",
    "            if s[0] == 'a':\n",
    "                mp[s].append(s)\n",
    "            else:\n",
    "                key =list(s)\n",
    "                # print(key)\n",
    "                for i in range(len(s)):\n",
    "                    key[i] = chr((ord(key[i]) - ord(s[0]) + 26) % 26 + ord('a')) #########\n",
    "                key =''.join(key)\n",
    "                # print(key)\n",
    "                mp[key].append(s)\n",
    "        \n",
    "        res = []\n",
    "        for mode, sublist in mp.items():\n",
    "            res.append(sublist)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def shift(s: str) -> str:\n",
    "            if s[0] == 'a':\n",
    "                return s\n",
    "            distance = ord(s[0])-ord('a')\n",
    "            ans = ''\n",
    "            for ch in s:\n",
    "                code = ord(ch) - distance\n",
    "                if code >= ord('a') and code <= ord('z'):\n",
    "                    ans += chr(code)\n",
    "                elif code < ord('a'):\n",
    "                    ans += chr(code+26)\n",
    "            return ans\n",
    "        # print(shift('ba'))\n",
    "        # print(shift('bcd'))\n",
    "        \n",
    "        dic=dict()\n",
    "        for s in strings:\n",
    "            shifted = shift(s)\n",
    "            if shifted not in dic:\n",
    "                dic[shifted] = [s]\n",
    "            else:\n",
    "                dic[shifted].append(s)\n",
    "        ans = []\n",
    "        for v in dic.values():\n",
    "            ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def get_diff(s):\n",
    "            diff = []\n",
    "            for i in range(1, len(s)):\n",
    "                d = ord(s[i]) - ord(s[i-1])\n",
    "                if d < 0:\n",
    "                    d += 26\n",
    "                diff.append(d)\n",
    "            return tuple(diff)\n",
    "        \n",
    "        res = defaultdict(list)\n",
    "        for s in strings:\n",
    "            d = get_diff(s)\n",
    "            res[d].append(s)\n",
    "        return [res[x] for x in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hash(word):\n",
    "            ret = 0\n",
    "            base = ord(word[0]) - ord('a') - 26\n",
    "            for c in word:\n",
    "                ret = ret * 26 + (ord(c) - base) % 26\n",
    "            return ret\n",
    "\n",
    "        d = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            d[hash(word)].append(word)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        record = collections.defaultdict(list)\n",
    "        mark = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            record[len(word)].append(word)\n",
    "        res = []\n",
    "        dp = collections.defaultdict(int)\n",
    "        for i in range(26):\n",
    "            dp[chr(i+ord('a'))] = i\n",
    "        for length in record:\n",
    "            array = record[length]\n",
    "            if len(array) == 1 or length == 1:\n",
    "                res.append(array)\n",
    "            else:\n",
    "                for i in range(len(array)):\n",
    "                    c = array[i]\n",
    "                    mark[tuple([(dp[c[i]]+26-dp[c[i-1]])%26 for i in range(1, length)])].append(c)\n",
    "        # print(mark)\n",
    "        for key in mark:\n",
    "            res.append(mark[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "\n",
    "        def str_to_idx(s):\n",
    "            ret = []\n",
    "            base = ord(s[0])\n",
    "            for c in s:\n",
    "                ret.append((ord(c)-base)%26)\n",
    "            return tuple(ret)\n",
    "\n",
    "        groups = {}\n",
    "        for s in strings:\n",
    "            k = str_to_idx(s)\n",
    "            if not k in groups:\n",
    "                groups[k] = []\n",
    "            groups[k].append(s)\n",
    "        return list(groups.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def genTuple(s):\n",
    "            cur = ord(s[0])\n",
    "            res = [0]\n",
    "            for l in s[1:]:\n",
    "                res.append((ord(l)-cur) % 26)\n",
    "            return tuple(res)\n",
    "        dic = dict()\n",
    "        for s in strings:\n",
    "            t = genTuple(s)\n",
    "            if t in dic:\n",
    "                dic[t].append(s)\n",
    "            else:\n",
    "                dic[t] = [s]\n",
    "        return [v for v in dic.values()]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def change_to_dis(word):\n",
    "            ans=[]\n",
    "            for i in range(len(word)-1):\n",
    "                ans.append((ord(word[i])-ord(word[i+1])+26)%26)\n",
    "            return ans\n",
    "        s=strings.copy()\n",
    "        for i in range(len(strings)):\n",
    "            strings[i]=[change_to_dis(strings[i]),i]\n",
    "        strings=sorted(strings,key=lambda x:x[0])\n",
    "        i=0\n",
    "        ret=[]\n",
    "        while i<len(strings):\n",
    "            ans=[]\n",
    "            ans.append(s[strings[i][1]])\n",
    "            i+=1\n",
    "            if i<len(strings):\n",
    "                while strings[i-1][0]==strings[i][0]:\n",
    "                    ans.append(s[strings[i][1]])\n",
    "                    i+=1\n",
    "                    if i==len(strings):\n",
    "                        break\n",
    "            \n",
    "            ret.append(ans)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = collections.defaultdict(list)\n",
    "        res = []\n",
    "\n",
    "        for s in strings:\n",
    "            val = 0\n",
    "            base = 1\n",
    "            for c in s:\n",
    "                diff = ord(c) - ord(s[0])\n",
    "                if diff <= 0:\n",
    "                    diff = 26 + diff\n",
    "                val += diff * base\n",
    "                base *= 10\n",
    "            dic[val].append(s)\n",
    "        print(dic)\n",
    "        return list(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def word_to_number(self, word):\n",
    "        if len(word)==1:\n",
    "            return ''\n",
    "\n",
    "        res = ''\n",
    "        for i in range(len(word)-1):\n",
    "            num = (ord(word[i+1])-ord(word[i]))%26\n",
    "            res += ' '+str(num)\n",
    "        return res\n",
    "\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        g_dict = defaultdict(list)\n",
    "        for word in strings:\n",
    "            g_dict[self.word_to_number(word)].append(word)\n",
    "\n",
    "        return list(g_dict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        def order(x):\n",
    "            if x < 0:\n",
    "                return x + 26\n",
    "            return x\n",
    "\n",
    "        for s in strings:\n",
    "            l = len(s)\n",
    "            d = [str(order(ord(s[i]) - ord(s[i+1]))) for i in range(l-1)]\n",
    "            key = str(l) + str('|') + ''.join(d)\n",
    "            dic[key].append(s)\n",
    "\n",
    "        return [dic[x] for x in dic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hashCounter(string):\n",
    "            return tuple(((ord(string[i])-ord(string[i-1]))%26) for i in range(1,len(string))) if len(string)>1 else 0\n",
    "        ans=defaultdict(list)\n",
    "        for s in strings:\n",
    "            ans[hashCounter(s)].append(s)\n",
    "        return list(ans.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            key = []\n",
    "            for i, ch in enumerate(s):\n",
    "                if i > 0:\n",
    "                    key.append((ord(s[i]) - ord(s[i-1]) + 26)%26)\n",
    "            d[tuple(key)].append(s)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for string in strings:\n",
    "            idx = [ord(i) for i in string]\n",
    "            mark = idx[0]\n",
    "            idx = [i-mark for i in idx]\n",
    "            idx = [str(i+26) if i < 0 else str(i) for i in idx]\n",
    "            idx = \" \".join(idx)\n",
    "            if idx not in res:\n",
    "                res[idx] = [string]\n",
    "            else:\n",
    "                res[idx].append(string)\n",
    "        return list(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        mp = defaultdict(list)\n",
    "        for s in strings :\n",
    "            if s[0] == 'a':\n",
    "                mp[s].append(s)\n",
    "            else:\n",
    "                key = list(s)\n",
    "                for i in range(len(s)):\n",
    "                    key[i] = chr( (ord(key[i]) - ord(s[0]) + 26) % 26 + ord('a') )\n",
    "                key = ''.join(key)\n",
    "                mp[key].append(s)\n",
    "\n",
    "        res = []\n",
    "        for mode, sublist in mp.items():\n",
    "            res.append(sublist)         \n",
    "\n",
    "        return  res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def check(s):\n",
    "            ans = []\n",
    "            for i in s:\n",
    "                ans.append(str((ord(i)-ord(s[0])) % 26))\n",
    "            return str(ans)\n",
    "        from collections import defaultdict\n",
    "        index = defaultdict(list)\n",
    "        for i in strings:\n",
    "            index[check(i)].append(i)\n",
    "        return list(index.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def check(s):\n",
    "            base = ord(s[0])\n",
    "            return tuple((base-ord(i)) % 26 for i in s)\n",
    "\n",
    "        from collections import defaultdict\n",
    "        index = defaultdict(list)\n",
    "        for i in strings:\n",
    "            index[check(i)].append(i)\n",
    "        return list(index.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        ret = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            diffs = []\n",
    "            for i in range(1, len(s)):\n",
    "                if s[i] > s[i - 1]:\n",
    "                    diff = ord(s[i]) - ord(s[i - 1])\n",
    "                else:\n",
    "                    diff = ord(s[i]) - ord(\"a\") + 1 + ord(\"z\") - ord(s[i - 1])\n",
    "                diffs.append(diff)\n",
    "            ret[tuple(diffs)].append(s)\n",
    "       \n",
    "        return [ret[k] for k in ret]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            # tmp = [0] * 26 # wrong!!!!!\n",
    "            tmp = []\n",
    "            for ch in word:\n",
    "                val = (ord(ch) - ord(word[0])) % 26 # -1%26=25\n",
    "                tmp.append(val)\n",
    "                # tmp[index] += 1 wrong\n",
    "            dic[tuple(tmp)].append(word) # [] not ()\n",
    "        return list(dic.values())\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        result=defaultdict(list)\n",
    "        for x in strings:\n",
    "            if len(x)<=1:\n",
    "                result[(0)].append(x)\n",
    "            else:\n",
    "                key=[]\n",
    "                for i in range(1,len(x)):\n",
    "                    key.append((ord(x[i])-ord(x[i-1]))%26)\n",
    "                # print(key)\n",
    "                result[tuple(key)].append(x)\n",
    "        return list(result.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]] :\n",
    "        mp = defaultdict(list)\n",
    "        for s in strings:\n",
    "            if s[0] == 'a':\n",
    "                mp[s].append(s)\n",
    "            else:\n",
    "                key = list(s)\n",
    "                for i, ch in enumerate(key):\n",
    "                    key[i] = chr((ord(key[i]) - ord(s[0]) + 26 ) % 26 + ord('a'))\n",
    "                key = \"\".join(key)\n",
    "                mp[key].append(s)\n",
    "\n",
    "        res = []\n",
    "        for key, value in mp.items():\n",
    "            res.append(value)\n",
    "\n",
    "        return  res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        c=defaultdict(list)\n",
    "        def get(word):\n",
    "            t=0\n",
    "            k=ord(word[0])-ord('a')\n",
    "            for w in word:\n",
    "                ws=ord(w)-ord('a')-k\n",
    "                if ws<0:ws+=26\n",
    "                t*=27\n",
    "                t+=ws+1\n",
    "            return t\n",
    "        for w in strings:\n",
    "            c[get(w)].append(w)\n",
    "        return list(c.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = collections.defaultdict(list) # hash: list\n",
    "        n = len(strings)\n",
    "        base = 1\n",
    "\n",
    "        for s in strings:\n",
    "            base = 1\n",
    "            hs = 0 \n",
    "            for c in s:\n",
    "                diff = ord(c) - ord(s[0])\n",
    "                if diff <= 0:\n",
    "                    diff += 26\n",
    "                hs = hs + diff * base\n",
    "                base *= 10\n",
    "            dic[hs].append(s)\n",
    "        \n",
    "        return list(dic.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = collections.defaultdict(list)\n",
    "\n",
    "        for s in strings:\n",
    "            base = 1\n",
    "            hashVal = 0\n",
    "            for i in range(len(s)):\n",
    "                diff = ord(s[i]) - ord(s[0])\n",
    "                if diff <= 0: # ==的情况不能+0，因为这样的话a,aa就是同一个key了，所以这里+26\n",
    "                    hashVal += (26 + diff) * base\n",
    "                else:\n",
    "                    hashVal += diff * base\n",
    "                base *= 10\n",
    "            dic[hashVal].append(s)\n",
    "        # print(dic)\n",
    "        \n",
    "        return list(dic.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        \"\"\"\n",
    "        Hash table [(diff_tuple) -> group_strings]\n",
    "        \"\"\"\n",
    "\n",
    "        def compute_diff_tuple(s: str) -> tuple[int, ...]:\n",
    "            diffs = []\n",
    "\n",
    "            for index in range(len(s) - 1):\n",
    "                diff = (ord(s[index + 1]) - ord(s[index])) % 26\n",
    "                diffs.append(diff)\n",
    "\n",
    "            return tuple(diffs)\n",
    "\n",
    "        from collections import defaultdict\n",
    "        diff_tuple_to_group_strings = defaultdict(list)\n",
    "\n",
    "        for string in strings:\n",
    "            diff_tuple = compute_diff_tuple(string)\n",
    "            diff_tuple_to_group_strings[diff_tuple].append(string)\n",
    "\n",
    "        return list(diff_tuple_to_group_strings.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        def order(x):\n",
    "            if x < 0:\n",
    "                return x + 26\n",
    "            return x\n",
    "\n",
    "        for s in strings:\n",
    "            l = len(s)\n",
    "            d = [str(order(ord(s[i]) - ord(s[i+1]))) for i in range(l-1)]\n",
    "            key = str(l) + str('|') + ''.join(d)\n",
    "            dic[key].append(s)\n",
    "\n",
    "        return [dic[x] for x in dic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        result=defaultdict(list)\n",
    "        for x in strings:\n",
    "            if len(x)<=1:\n",
    "                result[(0)].append(x)\n",
    "            else:\n",
    "                key=[]\n",
    "                for i in range(1,len(x)):\n",
    "                    key.append((ord(x[i])-ord(x[i-1]))%26)\n",
    "                # print(key)\n",
    "                result[tuple(key)].append(x)\n",
    "        return list(result.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        import collections\n",
    "        res = collections.defaultdict(list)\n",
    "        \n",
    "        def convert_to_relative(string):\n",
    "            if len(string) == 0:\n",
    "                return []\n",
    "            rela_distance = [0]\n",
    "            for i in range(1, len(string)):\n",
    "                if ord(string[i])-ord(string[i-1]) < 0:\n",
    "                    rela_distance.append(26+ord(string[i])-ord(string[i-1]))\n",
    "                else:\n",
    "                    rela_distance.append(ord(string[i])-ord(string[i-1]))\n",
    "            return \",\".join([str(x) for x in rela_distance])\n",
    "        \n",
    "        for string in strings:\n",
    "            rela_distance = convert_to_relative(string)\n",
    "            res[rela_distance].append(string)\n",
    "\n",
    "        return list(res.values())                                                                                          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def check(s):\n",
    "            return \"_\".join(str((ord(i) - ord(s[0])) % 26) for i in s)\n",
    "\n",
    "        from collections import defaultdict\n",
    "        index = defaultdict(list)\n",
    "        for i in strings:\n",
    "            index[check(i)].append(i)\n",
    "        return list(index.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def getv(s):\n",
    "            t = s[0]\n",
    "            res = []\n",
    "            for ss in s:\n",
    "                v = ord(ss)-ord(t)\n",
    "                if v < 0:\n",
    "                    v += 26\n",
    "                res.append(v)\n",
    "                t = ss\n",
    "            return str(res)\n",
    "\n",
    "        hs = {}\n",
    "        for ss in strings:\n",
    "            k = getv(ss)\n",
    "            if k not in hs:\n",
    "                hs[k] = [ss]\n",
    "            else:\n",
    "                hs[k].append(ss)\n",
    "\n",
    "        res = []\n",
    "        for k,v in hs.items():\n",
    "            res.append(v)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        map1 = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            temp = ()\n",
    "            for ch in s:\n",
    "                temp+=(ord(ch)- ord(s[0]))% 26, \n",
    "            map1[temp].append(s)\n",
    "        return list(map1.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        \n",
    "        def hash(org):\n",
    "            delta = ord(org[0]) - ord('a')\n",
    "            ret = \"\".join([chr(((ord(w) - delta) + 52) % 26) for w in org])\n",
    "            return ret\n",
    "\n",
    "        clips = defaultdict(list)\n",
    "\n",
    "        for s in strings:\n",
    "            clips[hash(s)].append(s)\n",
    "        return list(clips.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def check(s):\n",
    "            base = ord(s[0])\n",
    "            return tuple((ord(i) - base) % 26 for i in s)\n",
    "\n",
    "        from collections import defaultdict\n",
    "        index = defaultdict(list)\n",
    "        for i in strings:\n",
    "            index[check(i)].append(i)\n",
    "        return list(index.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "\n",
    "        def hashCounter(s):\n",
    "            if len(s) <= 1:\n",
    "                return (0)\n",
    "            return tuple(\n",
    "                (ord(s[i]) - ord(s[i-1])) % 26\n",
    "                for i in range(1, len(s))\n",
    "            )\n",
    "        \n",
    "        ans = defaultdict(list)\n",
    "\n",
    "        for s in strings:\n",
    "            ans[hashCounter(s)].append(s)\n",
    "\n",
    "        return list(ans.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        def order(x):\n",
    "            if x < 0:\n",
    "                return x + 26\n",
    "            return x\n",
    "\n",
    "        for s in strings:\n",
    "            l = len(s)\n",
    "            d = [str(order(ord(s[i]) - ord(s[i+1]))) for i in range(l-1)]\n",
    "            key = str(l) + str('|') + ''.join(d)\n",
    "            dic[key].append(s)\n",
    "\n",
    "        return [dic[x] for x in dic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        if strings == [\"\"]:\n",
    "            return [[\"\"]]\n",
    "        def hist(s):\n",
    "            re = []\n",
    "            for i in range(len(s)):\n",
    "                re.append( ord(s[i])-ord('a'))\n",
    "            first_value = re[0]\n",
    "            diff = first_value - 0\n",
    "            re = [(x - diff + 26) % 26 for x in re]\n",
    "            # min_value = min(re)\n",
    "            # re = [x - min_value for x in re]\n",
    "            # re = [x - 26 if x >= 13 else x for x in re]\n",
    "            # min_value = min(re)\n",
    "            # re = [x - min_value for x in re]\n",
    "            return tuple(re)\n",
    "        d = {}\n",
    "        for i in range(len(strings)):\n",
    "            m = hist(strings[i])\n",
    "            if m in d:\n",
    "                d[m].append(strings[i])\n",
    "            else:\n",
    "                d[m] = [strings[i]]\n",
    "        re = []\n",
    "        for k in d:\n",
    "            re.append(d[k])\n",
    "        # print(re)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        hashmap = {}\n",
    "        for s in strings:\n",
    "            t = []\n",
    "            for c in s:\n",
    "                c = chr((ord(c) - ord(s[0]) + 26) % 26 + ord('a'))\n",
    "                t.append(c)\n",
    "            key = \"\".join(t)\n",
    "            values = hashmap.get(key, [])\n",
    "            values.append(s)\n",
    "            hashmap[key] = values\n",
    "        \n",
    "        res = []\n",
    "        for key, values in hashmap.items():\n",
    "            res.append(values)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for string in strings:\n",
    "            idx = [ord(i) for i in string]\n",
    "            mark = idx[0]\n",
    "            idx = [i-mark for i in idx]\n",
    "            idx = [str(i+26) if i < 0 else str(i) for i in idx]\n",
    "            idx = \" \".join(idx)\n",
    "            if idx not in res:\n",
    "                res[idx] = [string]\n",
    "            else:\n",
    "                res[idx].append(string)\n",
    "        return list(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        groups= defaultdict(list)\n",
    "\n",
    "        def hashStr(s):\n",
    "            l = len(s)\n",
    "            hs = [l]\n",
    "            for i in range(l-1):\n",
    "                hs.append((ord(s[i+1]) - ord(s[i]))%26)\n",
    "            return tuple(hs)\n",
    "        \n",
    "        for s in strings:\n",
    "            hs = hashStr(s)\n",
    "            groups[hs].append(s)\n",
    "        \n",
    "        return list(groups.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:  \n",
    "        \"\"\"\n",
    "        map里面存后一位和前一位的差值\n",
    "        {(1,1): ['abc', 'bcd', 'xyz'], \n",
    "        (2,2,1): ['acef'], \n",
    "        (2,5): ['az', 'ba'], \n",
    "        (0): ['a', 'z']}\n",
    "        \"\"\"\n",
    "        map = defaultdict(list)\n",
    "        for string in strings:\n",
    "            diff = []\n",
    "            for i in range(1, len(string)):\n",
    "                diff.append(((ord(string[i]) - ord(string[i-1])) % 26))\n",
    "            \n",
    "            diff = tuple(diff)\n",
    "            map[diff].append(string)\n",
    "\n",
    "        result = []\n",
    "        for k, v in map.items():\n",
    "            result.append(v)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for string in strings:\n",
    "            idx = [ord(i) for i in string]\n",
    "            mark = idx[0]\n",
    "            idx = [i-mark for i in idx]\n",
    "            idx = [str(ord(\"z\")+i+1-ord(\"a\")) if i < 0 else str(i) for i in idx]\n",
    "            idx = \" \".join(idx)\n",
    "            if idx not in res:\n",
    "                res[idx] = [string]\n",
    "            else:\n",
    "                res[idx].append(string)\n",
    "        return list(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            key = []\n",
    "            for i, ch in enumerate(s):\n",
    "                if i > 0:\n",
    "                    key.append((ord(s[i]) - ord(s[i-1]) + 26)%26)\n",
    "            d[tuple(key)].append(s)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hash(string):\n",
    "            if len(string) == 0:\n",
    "                return tuple([0])\n",
    "            res = []\n",
    "            for i in range(len(string)-1):\n",
    "                res.append((ord(string[i+1])-ord(string[i]))%26)\n",
    "            return tuple(res)\n",
    "        \n",
    "        dic = {}\n",
    "        for s in strings:\n",
    "            if hash(s) not in dic:\n",
    "                dic[hash(s)] = [s]\n",
    "            else:\n",
    "                dic[hash(s)].append(s)\n",
    "        return list(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        pattern_dict = defaultdict(list)\n",
    "        for s in strings:\n",
    "            pattern = self.converted(s)\n",
    "            pattern_dict[pattern].append(s)\n",
    "        return list(pattern_dict.values())\n",
    "    \n",
    "    def converted(self, s):\n",
    "        l = [0]\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            l.append((ord(s[i]) - ord(s[i-1]) + 26) % 26)\n",
    "        return tuple(l)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dis_arrs = collections.defaultdict(list)\n",
    "        for string in strings:\n",
    "            dis = []\n",
    "            i = 1\n",
    "            while i < len(string):\n",
    "                dis.append(str((ord(string[i]) - ord(string[i-1])) % 26))\n",
    "                i += 1\n",
    "            dis_arrs[\".\".join(dis)].append(string)\n",
    "        \n",
    "        return list(dis_arrs.values())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for string in strings:\n",
    "            idx = [ord(i) for i in string]\n",
    "            mark = idx[0]\n",
    "            idx = [i-mark for i in idx]\n",
    "            idx = [str(ord(\"z\")+i+1-ord(\"a\")) if i < 0 else str(i) for i in idx]\n",
    "            idx = \" \".join(idx)\n",
    "            if idx not in res:\n",
    "                res[idx] = [string]\n",
    "            else:\n",
    "                res[idx].append(string)\n",
    "        print(res)\n",
    "        print(ord(\"a\"))\n",
    "        return list(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def word_to_number(self, word):\n",
    "        res = ''\n",
    "        if len(word) == 1:\n",
    "            return ''\n",
    "        for i in range(len(word) - 1):\n",
    "            num = (ord(word[i + 1]) - ord(word[i]))%26\n",
    "            res += ',' + str(num)\n",
    "        return res\n",
    "        ### key 是总结出来的字母之间的差值\n",
    "\n",
    "    def groupStrings(self, strings: list[str]) -> list[list[str]]:\n",
    "        group_dict = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            group_dict[self.word_to_number(word)].append(word)\n",
    "        #print(group_dict)\n",
    "        return list(group_dict.values())\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dt=dict()\n",
    "        def getK(s):\n",
    "            res=[]\n",
    "            for i in range(1,len(s)):\n",
    "                dx=ord(s[i])-ord(s[i-1])\n",
    "                if dx<0:dx+=26\n",
    "                res.append(dx)\n",
    "            return tuple(res)\n",
    "        for i in strings:\n",
    "            key=getK(i)\n",
    "            if key in dt:\n",
    "                dt[key].append(i)\n",
    "            else:\n",
    "                dt[key]=[i]\n",
    "        print(dt)\n",
    "        ans=[]\n",
    "        for (key,val) in dt.items():\n",
    "            ans.append(val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        cnt = defaultdict(list)\n",
    "        res = []\n",
    "        j = 0\n",
    "        for s in strings:\n",
    "            if len(s) == 1:\n",
    "                if not res:\n",
    "                    res.append([s])\n",
    "                    cnt[j] = []\n",
    "                    j += 1\n",
    "                else:\n",
    "                    if [] not in cnt.values():\n",
    "                        cnt[j] = []\n",
    "                        j += 1\n",
    "                    for k in cnt:\n",
    "                        if cnt[k] == []:\n",
    "                            if k >= len(res):\n",
    "                                res.append([s])\n",
    "                            else:\n",
    "                                res[k].append(s)\n",
    "            else:\n",
    "                a = []\n",
    "                for i in range(1, len(s)):\n",
    "                    a.append((ord(s[i]) - ord(s[i - 1])) % 26)\n",
    "                if a in cnt.values():\n",
    "                    for k in cnt:\n",
    "                        if cnt[k] == a:\n",
    "                            res[k].append(s)\n",
    "                else:\n",
    "                    cnt[j] = a \n",
    "                    res.append([s])\n",
    "                    j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        self.parents = list(range(len(strings)))\n",
    "        for i in range(len(strings)):\n",
    "            for j in range(i + 1, len(strings)):\n",
    "                if self.check(strings[i], strings[j]):\n",
    "                    root_a = self.get_root(i)\n",
    "                    root_b = self.get_root(j)\n",
    "                    self.parents[root_b] = root_a\n",
    "        print(self.parents)\n",
    "        ans = {}\n",
    "        for i in range(len(strings)):\n",
    "            if self.parents[i] not in ans:\n",
    "                ans[self.parents[i]] = []\n",
    "            ans[self.parents[i]].append(strings[i])\n",
    "        return [_ for _ in ans.values()]\n",
    "\n",
    "\n",
    "    def get_root(self, i):\n",
    "        if self.parents[i] != i:\n",
    "            self.parents[i] = self.get_root(self.parents[i])\n",
    "        return self.parents[i]\n",
    "\n",
    "    def check(self, a, b):\n",
    "        if len(a) != len(b):\n",
    "            return False\n",
    "        interval = (ord(a[0]) - ord(b[0])) % 26\n",
    "        # print(a, b, interval)\n",
    "        for i, j in zip(a[1:], b[1:]):\n",
    "            if (ord(i) - ord(j)) % 26 != interval:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        dic = collections.defaultdict(list)\n",
    "        for strs in strings:\n",
    "            tmp = []\n",
    "            start = strs[0]\n",
    "            for ch in strs:\n",
    "                x = ord(start) - ord(ch)\n",
    "                x = x % 26 # % 26!!!!\n",
    "                tmp.append(x)\n",
    "            dic[tuple(tmp)].append(strs)\n",
    "        return list(dic.values())\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        return self.answer_1(strings)\n",
    "\n",
    "    def answer_1(self, strings):\n",
    "        storage = collections.defaultdict(list)\n",
    "\n",
    "        for word in strings:\n",
    "            key = self._get_word_key(word)\n",
    "            storage[key].append(word)\n",
    "        return list(storage.values())\n",
    "\n",
    "    @classmethod\n",
    "    def _get_word_key(cls, word):\n",
    "        word_len = len(word)\n",
    "\n",
    "        if word_len == 1:\n",
    "            return \"\"\n",
    "\n",
    "        key = \"\"\n",
    "\n",
    "        for index in range(word_len - 1):\n",
    "            key_char = (ord(word[index + 1]) - ord(word[index]) + 26) % 26\n",
    "            key += str(key_char) + \",\"\n",
    "        return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def word_to_number(self, word):\n",
    "        res = ''\n",
    "        if len(word) == 1:\n",
    "            return ''\n",
    "        for i in range(len(word) - 1):\n",
    "            num = (ord(word[i + 1]) - ord(word[i]))%26\n",
    "            res += ',' + str(num)\n",
    "        return res\n",
    "\n",
    "    def groupStrings(self, strings: list[str]) -> list[list[str]]:\n",
    "        group_dict = defaultdict(list)\n",
    "        for word in strings:\n",
    "            group_dict[self.word_to_number(word)].append(word)\n",
    "        return list(group_dict.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        hashmap = {}\n",
    "        for word in strings:\n",
    "            key = []\n",
    "            for char in word:\n",
    "                print(char)\n",
    "                shifted_char = chr((ord(char) - ord(word[0]) + 26) % 26 + ord('a'))\n",
    "                print(shifted_char)\n",
    "                print()\n",
    "                key.append(shifted_char)\n",
    "            key_str = ''.join(key)\n",
    "            # if key_str not in hashmap:\n",
    "            #     hashmap[key_str] = []\n",
    "            \n",
    "            # hashmap[key_str].append(word)\n",
    "            hashmap[key_str]=hashmap.get(key_str,[])\n",
    "            hashmap[key_str].append(word)\n",
    "        return list(hashmap.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "        \n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        fa = list(range(n)) \n",
    "        rank = [0] * n\n",
    "        d = dict()\n",
    "        \n",
    "        def find(x):\n",
    "            while x != fa[x]:\n",
    "                x = fa[x]\n",
    "            return x\n",
    "            \n",
    "        def merge(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                if rank[fx] > rank[fy]:\n",
    "                    # rank[fx] += rank[fy]\n",
    "                    fa[fy] = fx\n",
    "                else:\n",
    "                    if rank[y] == rank[x]:\n",
    "                        rank[fy] = rank[fx] + 1\n",
    "                    fa[fx] = fy\n",
    "        \n",
    "        \n",
    "                \n",
    "        def go(newstatus, i):\n",
    "            old = d.get(newstatus)\n",
    "            if old is not None:\n",
    "                merge(old, i)\n",
    "                    \n",
    "        for wi in range(n):\n",
    "            w = words[wi]\n",
    "           \n",
    "            status = 0\n",
    "            for c in w:\n",
    "                status |= 1 << (ord(c) - ord('a'))\n",
    "            old = d.get(status)\n",
    "            if old is not None:\n",
    "                merge(old, wi)\n",
    "                continue\n",
    "            for i in range(26):\n",
    "                if status & 1 << i:\n",
    "                    go(status ^ 1 << i, wi)\n",
    "                    for j in range(26):\n",
    "                        if status & 1 << j == 0:\n",
    "                            go((status ^ 1 << i) ^ 1 << j, wi)\n",
    "                else:\n",
    "                    go(status | 1 << i, wi)\n",
    "                    \n",
    "            d[status] = wi\n",
    "        ret = [0, 0]\n",
    "        cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            f = find(i)\n",
    "            cnt[f] += 1\n",
    "            ret[1] = max(ret[1], cnt[f])\n",
    "            if i == f:\n",
    "                ret[0] += 1\n",
    "        return ret\n",
    "               \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "        \n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        fa = list(range(n)) \n",
    "        rank = [1] * n\n",
    "        d = dict()\n",
    "        \n",
    "        def find(x):\n",
    "            while x != fa[x]:\n",
    "                x = fa[x]\n",
    "            return x\n",
    "            \n",
    "        def merge(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                if rank[fx] > rank[fy]:\n",
    "                    rank[fx] += rank[fy]\n",
    "                    fa[fy] = fx\n",
    "                else:\n",
    "                    rank[fy] += rank[fx]\n",
    "                    fa[fx] = fy\n",
    "        \n",
    "        \n",
    "                \n",
    "        def go(newstatus, i):\n",
    "            old = d.get(newstatus)\n",
    "            if old is not None:\n",
    "                merge(old, i)\n",
    "                    \n",
    "        for wi in range(n):\n",
    "            w = words[wi]\n",
    "           \n",
    "            status = 0\n",
    "            for c in w:\n",
    "                status |= 1 << (ord(c) - ord('a'))\n",
    "            old = d.get(status)\n",
    "            if old is not None:\n",
    "                merge(old, wi)\n",
    "                continue\n",
    "            for i in range(26):\n",
    "                if status & 1 << i:\n",
    "                    go(status ^ 1 << i, wi)\n",
    "                    for j in range(26):\n",
    "                        if status & 1 << j == 0:\n",
    "                            go((status ^ 1 << i) ^ 1 << j, wi)\n",
    "                else:\n",
    "                    go(status | 1 << i, wi)\n",
    "                    \n",
    "            d[status] = wi\n",
    "        ret = [0, 0]\n",
    "        for i in range(n):\n",
    "            if i == fa[i]:\n",
    "                ret[0] += 1\n",
    "                if ret[1] < rank[i]:\n",
    "                    ret[1] = rank[i]\n",
    "        return ret\n",
    "               \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        ordA = ord('a')\n",
    "        def word2mask(w):\n",
    "            return reduce(or_, (1 << (ord(c) - ordA) for c in w))\n",
    "        byLen = defaultdict(set)\n",
    "        maskCount = Counter()\n",
    "        for w in words:\n",
    "            m = word2mask(w)\n",
    "            byLen[len(w)].add(m)\n",
    "            maskCount[m] += 1\n",
    "        lastL = -1\n",
    "        parentMap = {}\n",
    "        def parent(x):\n",
    "            stack = []\n",
    "            while (y:=parentMap.get(x, x)) != x:\n",
    "                stack.append(x)\n",
    "                x = y\n",
    "            for y in stack:\n",
    "                parentMap[y] = x\n",
    "            return x\n",
    "        def combine(m1, m2):\n",
    "            p1, p2 = parent(m1), parent(m2)\n",
    "            if p1 == p2: return\n",
    "            if p2 < p1:\n",
    "                p1, p2 = p2, p1\n",
    "            parentMap[p2] = p1\n",
    "        for l in sorted(byLen.keys()):\n",
    "            maskSet = byLen[l]\n",
    "            for m1, m2 in combinations(maskSet, 2):\n",
    "                if (m1 ^ m2).bit_count() == 2:\n",
    "                    combine(m1, m2)\n",
    "            if l - lastL == 1:\n",
    "                lastMaskSet = byLen[lastL]\n",
    "                for m1, m2 in product(lastMaskSet, maskSet):\n",
    "                    if m2 > m1 and (m2 - m1).bit_count() == 1:\n",
    "                        combine(m1, m2)\n",
    "            lastL = l\n",
    "        groupCount = Counter()\n",
    "        for k in chain.from_iterable(byLen.values()):\n",
    "            pk = parent(k)\n",
    "            groupCount[pk] += maskCount[k]\n",
    "        return [len(groupCount), groupCount.most_common(1)[0][1]]\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.part = n\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        '''\n",
    "        寻找 x 的根节点\n",
    "        '''\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> bool:\n",
    "        '''\n",
    "        合并 x 和 y 所在的树\n",
    "        '''\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        # 合并到点较多的块上\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def inTheSamePart(self, x: int, y: int) -> bool:\n",
    "        '''\n",
    "        判断 x 和 y 是否在同一个树\n",
    "        '''\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def getPartSize(self, x: int) -> int:\n",
    "        '''\n",
    "        返回 x 所在树的节点个数\n",
    "        '''\n",
    "        root_x = self.find(x)\n",
    "        return self.size[root_x]\n",
    "from string import * \n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        uf = UnionFind(n)\n",
    "        nums = []\n",
    "        for word in words:\n",
    "            state = 0\n",
    "            for ch in word:\n",
    "                state |= 1 << (ord(ch) - ord('a'))\n",
    "            nums.append(state)\n",
    "        \n",
    "        dic = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in dic:\n",
    "                uf.union(i, dic[num])\n",
    "            else:\n",
    "                dic[num] = i\n",
    "        \n",
    "        for num in dic.keys():\n",
    "            have = set()\n",
    "            re = set()\n",
    "            for i in range(26):\n",
    "                if num & 1 << i == 0:\n",
    "                    t = num | 1 << i\n",
    "                    if t in dic:\n",
    "                        uf.union(dic[num], dic[t])\n",
    "                    \n",
    "                    re.add(i)\n",
    "                else:\n",
    "                    have.add(i)\n",
    "            for i in re:\n",
    "                state = num | 1 << i\n",
    "                for j in have:\n",
    "                    state &= ~(1 << j)\n",
    "                    if state in dic:\n",
    "                        uf.union(dic[num], dic[state])\n",
    "                    state |= 1 << j\n",
    "\n",
    "        return [uf.part, max(uf.size)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.F = [i for i in range(n)]\n",
    "        self.cnt = [1 for i in range(n)]\n",
    "        self.res = n\n",
    "    \n",
    "    def find(self,x):\n",
    "        return x if self.F[x] == x else self.find(self.F[x])\n",
    "    \n",
    "    def union(self,a,b):\n",
    "        fa,fb = self.find(a),self.find(b)\n",
    "        if self.cnt[fa] >= self.cnt[fb]:\n",
    "            self.cnt[fa] += self.cnt[fb]\n",
    "            self.F[fb] = fa\n",
    "        else:\n",
    "            self.cnt[fb] += self.cnt[fa]\n",
    "            self.F[fa] = fb\n",
    "        self.res -= 1\n",
    "            \n",
    "def f(s):\n",
    "    res = 0\n",
    "    for c in s:\n",
    "        res += 1 << (ord(c)-ord('a'))\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        UF = UnionFind(n)\n",
    "        L = []\n",
    "        for i in words:\n",
    "            L.append(f(i))\n",
    "        G = defaultdict(list)\n",
    "        D = {}\n",
    "        for idx,i in enumerate(L):\n",
    "            G[i].append(idx)\n",
    "        for i,l in G.items():\n",
    "            nl = len(l)\n",
    "            if nl == 1:D[i] = l[0];continue\n",
    "            for j in range(1,nl):\n",
    "                UF.union(l[0],l[j])\n",
    "            D[i] = UF.find(l[0])\n",
    "        for v in D:\n",
    "            #add & minus\n",
    "            for i in range(26):\n",
    "                nv = v ^ 1 << i\n",
    "                if nv not in D:continue\n",
    "                if UF.find(D[nv]) == UF.find(D[v]):continue\n",
    "                UF.union(D[nv],D[v])\n",
    "            #change\n",
    "            S = set();pos = 0;kv = v\n",
    "            while kv:\n",
    "                if kv % 2:S.add(pos)\n",
    "                pos += 1;kv >>= 1\n",
    "            for mi in S:\n",
    "                for ad in range(26):\n",
    "                    if ad in S:continue\n",
    "                    nv = (v | 1 << ad) ^ 1 << mi\n",
    "                    if nv not in D:continue\n",
    "                    if UF.find(D[nv]) == UF.find(D[v]):continue\n",
    "                    UF.union(D[nv],D[v])\n",
    "        return [UF.res,max(UF.cnt)]\n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "        \n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        fa = list(range(n)) \n",
    "        rank = [0] * n\n",
    "        d = dict()\n",
    "        \n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "            \n",
    "        def merge(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                if rank[fx] > rank[fy]:\n",
    "                    # rank[fx] += rank[fy]\n",
    "                    fa[fy] = fx\n",
    "                else:\n",
    "                    if rank[y] == rank[x]:\n",
    "                        rank[fy] = rank[fx] + 1\n",
    "                    fa[fx] = fy\n",
    "        \n",
    "        \n",
    "                \n",
    "        def go(newstatus, i):\n",
    "            old = d.get(newstatus)\n",
    "            if old is not None:\n",
    "                merge(old, i)\n",
    "                    \n",
    "        for wi in range(n):\n",
    "            w = words[wi]\n",
    "           \n",
    "            status = 0\n",
    "            for c in w:\n",
    "                status |= 1 << (ord(c) - ord('a'))\n",
    "            old = d.get(status)\n",
    "            if old is not None:\n",
    "                merge(old, wi)\n",
    "                continue\n",
    "            for i in range(26):\n",
    "                if status & 1 << i:\n",
    "                    go(status ^ 1 << i, wi)\n",
    "                    for j in range(26):\n",
    "                        if status & 1 << j == 0:\n",
    "                            go((status ^ 1 << i) ^ 1 << j, wi)\n",
    "                else:\n",
    "                    go(status | 1 << i, wi)\n",
    "                    \n",
    "            d[status] = wi\n",
    "        ret = [0, 0]\n",
    "        cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            f = find(i)\n",
    "            cnt[f] += 1\n",
    "            ret[1] = max(ret[1], cnt[f])\n",
    "            if i == f:\n",
    "                ret[0] += 1\n",
    "        return ret\n",
    "               \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        \n",
    "        n = len(words)\n",
    "        pa = list(range(n))\n",
    "        we = [1] * n\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        def union(i,j):\n",
    "            x,y = map(find,[i,j])\n",
    "            if x == y: return\n",
    "            if we[x] < we[y]: x,y = y,x\n",
    "            pa[y] = x\n",
    "            we[x] += we[y]\n",
    "        \n",
    "        di = dict()\n",
    "        for i,w in enumerate(words):\n",
    "            s = 0\n",
    "            for c in w: s |= 1<<(ord(c)-ord('a'))\n",
    "            if s in di: union(i,di[s])\n",
    "            else: di[s] = i\n",
    "        \n",
    "        for x,i in di.items():\n",
    "            for j in range(26):\n",
    "                if x ^ (1<<j) in di: union(i,di[x^(1<<j)])\n",
    "                if not x & (1<<j): continue\n",
    "                t = x^(1<<j)\n",
    "                for k in range(26):\n",
    "                    if k == j: continue\n",
    "                    if t & (1<<k): continue\n",
    "                    if t | (1<<k) in di: union(i,di[t|(1<<k)])\n",
    "        \n",
    "        for i in range(n): find(i)\n",
    "        return len(set(pa)),max(we)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        \n",
    "        n = len(words)\n",
    "        pa = list(range(n))\n",
    "        we = [1] * n\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        def union(i,j):\n",
    "            x,y = map(find,[i,j])\n",
    "            if x == y: return\n",
    "            if we[x] < we[y]: x,y = y,x\n",
    "            pa[y] = x\n",
    "            we[x] += we[y]\n",
    "        \n",
    "        di = dict()\n",
    "        for i,w in enumerate(words):\n",
    "            x = 0\n",
    "            for c in w: x |= 1<<(ord(c)-ord('a'))\n",
    "            if x in di:\n",
    "                union(i,di[x])\n",
    "                continue\n",
    "            else: di[x] = i\n",
    "            for j in range(26):\n",
    "                if x ^ (1<<j) in di: union(i,di[x^(1<<j)])\n",
    "                if not x & (1<<j): continue\n",
    "                t = x^(1<<j)\n",
    "                for k in range(26):\n",
    "                    if k == j: continue\n",
    "                    if t & (1<<k): continue\n",
    "                    if t | (1<<k) in di: union(i,di[t|(1<<k)])\n",
    "        \n",
    "        for i in range(n): find(i)\n",
    "        return len(set(pa)),max(we)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        # 并查集模板（哈希表写法）\n",
    "        fa, size = {}, defaultdict(int)\n",
    "        groups, max_size = len(words), 0\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int):\n",
    "            nonlocal groups, max_size\n",
    "            if y not in fa:\n",
    "                return\n",
    "            x, y = find(x), find(y)\n",
    "            if x == y:\n",
    "                return\n",
    "            fa[x] = y\n",
    "            size[y] += size[x]\n",
    "            max_size = max(max_size, size[y])  # 维护答案\n",
    "            groups -= 1\n",
    "\n",
    "        for word in words:\n",
    "            x = 0\n",
    "            for ch in word:\n",
    "                x |= 1 << (ord(ch) - ord('a'))  # 计算 word 的二进制表示\n",
    "            fa[x] = x  # 添加至并查集\n",
    "            size[x] += 1\n",
    "            max_size = max(max_size, size[x])  # 维护答案\n",
    "            if size[x] > 1:\n",
    "                groups -= 1\n",
    "\n",
    "        for x in fa:  # 枚举所有字符串（二进制表示）\n",
    "            for i in range(26):\n",
    "                merge(x, x ^ (1 << i))  # 添加或删除字符 i\n",
    "                if (x >> i) & 1:\n",
    "                    for j in range(26):\n",
    "                        if ((x >> j) & 1) == 0:\n",
    "                            merge(x, x ^ (1 << i) | (1 << j))  # 替换字符 i 为 j\n",
    "        return [groups, max_size]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        # 给定字符串数组，分为不关联的子序列，能分为多少组：同组元素课相互转换，添加，删除，替换任一字母\n",
    "        # 并查集分组：图的连通分量\n",
    "        # 哈希并查集 + 位运算\n",
    "        # 枚举words中的字符串s，并枚举s通过操作得到的新字符串t，如果t再words中，s，t可以分到一组。可以用并查集关联可以分到一组的字符串\n",
    "\n",
    "        # 并查集模板(哈希表写法)\n",
    "        fa, size = {}, defaultdict(int)\n",
    "        groups, max_size = len(words), 0\n",
    "        def find(x:int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x:int, y:int):\n",
    "            nonlocal groups, max_size\n",
    "            if y not in fa:\n",
    "                return \n",
    "            x, y = find(x), find(y)\n",
    "            if x == y:\n",
    "                return \n",
    "            fa[x] = y\n",
    "            size[y] += size[x]\n",
    "            max_size = max(max_size, size[y]) # 维护答案\n",
    "            groups -= 1 # 分组数， 每次合并后减一\n",
    "\n",
    "        for word in words:\n",
    "            x = 0\n",
    "            for ch in word:\n",
    "                x |= 1 << (ord(ch) - ord('a')) # 计算word 的二进制表示\n",
    "            fa[x] = x # 添加到并查集\n",
    "            size[x]  += 1\n",
    "            max_size = max(max_size, size[x]) # 维护答案\n",
    "            if size[x] > 1:\n",
    "                groups -= 1\n",
    "        \n",
    "        for x in fa: # 枚举所有字符串(二进制表示)\n",
    "            for i in range(26):\n",
    "                merge(x, x ^ (1 << i)) # 添加或删除字符i\n",
    "                if (x >> i) & 1:\n",
    "                    for j in range(26): \n",
    "                        if ((x >> j) & 1) == 0: # 判断字符变化一次后相同，并为一组\n",
    "                            merge(x, x ^ (1 << i) | (1 << j)) # 替换字符i为j\n",
    "        return [groups, max_size]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        # 哈希并查集 + 位运算\n",
    "        # 枚举words中的字符串s，并枚举s通过操作得到的新字符串t，如果t再words中，s，t可以分到一组。可以用并查集关联可以分到一组的字符串\n",
    "\n",
    "        # 并查集模板(哈希表写法)\n",
    "        fa, size = {}, defaultdict(int)\n",
    "        groups, max_size = len(words), 0\n",
    "        def find(x:int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x:int, y:int):\n",
    "            nonlocal groups, max_size\n",
    "            if y not in fa:\n",
    "                return \n",
    "            x, y = find(x), find(y)\n",
    "            if x == y:\n",
    "                return \n",
    "            fa[x] = y\n",
    "            size[y] += size[x]\n",
    "            max_size = max(max_size, size[y]) # 维护答案\n",
    "            groups -= 1\n",
    "            \n",
    "        for word in words:\n",
    "            x = 0\n",
    "            for ch in word:\n",
    "                x |= 1 << (ord(ch) - ord('a')) # 计算word 的二进制表示\n",
    "            fa[x] = x # 添加到并查集\n",
    "            size[x]  += 1\n",
    "            max_size = max(max_size, size[x]) # 维护答案\n",
    "            if size[x] > 1:\n",
    "                groups -= 1\n",
    "        \n",
    "        for x in fa: # 枚举所有字符串(二进制表示)\n",
    "            for i in range(26):\n",
    "                merge(x, x ^ (1 << i)) # 添加或删除字符i\n",
    "                if (x >> i) & 1:\n",
    "                    for j in range(26):\n",
    "                        if ((x >> j) & 1) == 0:\n",
    "                            merge(x, x ^ (1 << i) | (1 << j)) # 替换字符i为j\n",
    "        return [groups, max_size]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        # 并查集模板（哈希表写法）\n",
    "        fa, size = {}, defaultdict(int)\n",
    "        groups, max_size = len(words), 0\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int):\n",
    "            nonlocal groups, max_size\n",
    "            if y not in fa:\n",
    "                return\n",
    "            x, y = find(x), find(y)\n",
    "            if x == y:\n",
    "                return\n",
    "            fa[x] = y\n",
    "            size[y] += size[x]\n",
    "            max_size = max(max_size, size[y])  # 维护答案\n",
    "            groups -= 1\n",
    "\n",
    "        for word in words:\n",
    "            x = 0\n",
    "            for ch in word:\n",
    "                x |= 1 << (ord(ch) - ord('a'))  # 计算 word 的二进制表示\n",
    "            fa[x] = x  # 添加至并查集\n",
    "            size[x] += 1\n",
    "            max_size = max(max_size, size[x])  # 维护答案\n",
    "            if size[x] > 1:\n",
    "                groups -= 1\n",
    "\n",
    "        for x in fa:  # 枚举所有字符串（二进制表示）\n",
    "            for i in range(26):\n",
    "                merge(x, x ^ (1 << i))  # 添加或删除字符 i\n",
    "                if (x >> i) & 1:\n",
    "                    for j in range(26):\n",
    "                        if ((x >> j) & 1) == 0:\n",
    "                            merge(x, x ^ (1 << i) | (1 << j))  # 替换字符 i 为 j\n",
    "        return [groups, max_size]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\r\n",
    "        # 并查集模板（哈希表写法）\r\n",
    "        fa, size = {}, defaultdict(int)\r\n",
    "        groups, max_size = len(words), 0\r\n",
    "        def find(x: int) -> int:\r\n",
    "            if fa[x] != x:\r\n",
    "                fa[x] = find(fa[x])\r\n",
    "            return fa[x]\r\n",
    "        def merge(x: int, y: int):\r\n",
    "            nonlocal groups, max_size\r\n",
    "            if y not in fa:\r\n",
    "                return\r\n",
    "            x, y = find(x), find(y)\r\n",
    "            if x == y:\r\n",
    "                return\r\n",
    "            fa[x] = y\r\n",
    "            size[y] += size[x]\r\n",
    "            max_size = max(max_size, size[y])  # 维护答案\r\n",
    "            groups -= 1\r\n",
    "\r\n",
    "        for word in words:\r\n",
    "            x = 0\r\n",
    "            for ch in word:\r\n",
    "                x |= 1 << (ord(ch) - ord('a'))  # 计算 word 的二进制表示\r\n",
    "            fa[x] = x  # 添加至并查集\r\n",
    "            size[x] += 1\r\n",
    "            max_size = max(max_size, size[x])  # 维护答案\r\n",
    "            if size[x] > 1:\r\n",
    "                groups -= 1\r\n",
    "\r\n",
    "        for x in fa:  # 枚举所有字符串（二进制表示）\r\n",
    "            for i in range(26):\r\n",
    "                merge(x, x ^ (1 << i))  # 添加或删除字符 i\r\n",
    "                if (x >> i) & 1:\r\n",
    "                    for j in range(26):\r\n",
    "                        if ((x >> j) & 1) == 0:\r\n",
    "                            merge(x, x ^ (1 << i) | (1 << j))  # 替换字符 i 为 j\r\n",
    "        return [groups, max_size]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        fa = []\n",
    "        size = []\n",
    "        d = {}\n",
    "        for word in words:\n",
    "            cur = [0] * 26\n",
    "            for c in word:\n",
    "                cur[ord(c) - ord('a')] = 1\n",
    "            f = tuple(cur)\n",
    "            if f in d:\n",
    "                size[d[f]] += 1\n",
    "            else:\n",
    "                d[f] = len(size)\n",
    "                fa.append(len(size))\n",
    "                size.append(1)\n",
    "        group = len(d)\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(x, y):\n",
    "            nonlocal group\n",
    "            a, b = find(x), find(y)\n",
    "            if a == b:\n",
    "                return\n",
    "            if a < b:\n",
    "                fa[b] = a\n",
    "                size[a] += size[b]\n",
    "            else:\n",
    "                fa[a] = b\n",
    "                size[b] += size[a]\n",
    "            group -= 1\n",
    "        \n",
    "        for f in d:\n",
    "            cur = list(f)\n",
    "            # delete\n",
    "            if sum(cur) > 1:\n",
    "                for i in range(26):\n",
    "                    if cur[i] > 0:\n",
    "                        cur[i] = 0\n",
    "                        g = tuple(cur)\n",
    "                        if g in d:\n",
    "                            merge(d[f], d[g])\n",
    "                        cur[i] = 1\n",
    "            # add & replace\n",
    "            if sum(cur) < 26:\n",
    "                space = []\n",
    "                for i in range(26):\n",
    "                    if cur[i] == 0:\n",
    "                        space.append(i)\n",
    "                        cur[i] = 1\n",
    "                        g = tuple(cur)\n",
    "                        if g in d:\n",
    "                            merge(d[f], d[g])\n",
    "                        cur[i] = 0\n",
    "                for i in range(26):\n",
    "                    if cur[i] == 1:\n",
    "                        cur[i] = 0\n",
    "                        for idx in space:\n",
    "                            cur[idx] = 1\n",
    "                            g = tuple(cur)\n",
    "                            if g in d:\n",
    "                                merge(d[f], d[g])\n",
    "                            cur[idx] = 0\n",
    "                        cur[i] = 1              \n",
    "        return [group, max(size)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def w2b(w):\n",
    "    b = 0\n",
    "    for x in w:\n",
    "        b |= (1 << (ord(x) - ord('a')))\n",
    "\n",
    "    return b\n",
    "\n",
    "def validate(x):\n",
    "    return x == 0 or x & (x - 1) == 0\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        nums = [w2b(w) for w in words]\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        fa = {}\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i] = find(fa[i])\n",
    "                return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            fa[x] = x\n",
    "\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "\n",
    "            for i in range(26):\n",
    "                y = x ^ (1 << i)\n",
    "\n",
    "                if y in fa:\n",
    "                    merge(x, y)\n",
    "\n",
    "                if (x >> i) & 1:\n",
    "                    for j in range(26):\n",
    "                        if ((x >> j) & 1) == 0:\n",
    "                            y = x ^ (1 << i) ^ (1 << j)\n",
    "\n",
    "                            if y in fa:\n",
    "                                merge(x, y)\n",
    "\n",
    "\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        for x in nums:\n",
    "            d[find(x)] += 1\n",
    "\n",
    "        return len(d), max(d.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        pa = {}\n",
    "        cnt = defaultdict(lambda: 0)\n",
    "        ans = [0, 1]\n",
    "        for w in words:\n",
    "            v = 0\n",
    "            for c in w:\n",
    "                v |= 1 << (ord(c) - ord('a'))\n",
    "            pa[v] = v\n",
    "            cnt[v] += 1\n",
    "            ans[1] = max(ans[1], cnt[v])\n",
    "            if cnt[v] == 1: ans[0] += 1\n",
    "\n",
    "        def find(x):\n",
    "            if x not in pa: return -1\n",
    "            if x == pa[x]: return x\n",
    "            pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "\n",
    "        def merge(r0, r1):\n",
    "            if r1 == -1 or r0 == r1: return\n",
    "            pa[r1] = r0\n",
    "            cnt[r0] += cnt[r1]\n",
    "            ans[0] -= 1\n",
    "            ans[1] = max(ans[1], cnt[r0])\n",
    "\n",
    "        for v in cnt.keys():\n",
    "            r0 = find(v)\n",
    "            # del\n",
    "            for i in range(v.bit_length()):\n",
    "                if v & (1 << i):\n",
    "                    r1 = find(v - (1 << i))\n",
    "                    merge(r0, r1)\n",
    "            # add\n",
    "            for i in range(v.bit_length()):\n",
    "                if v & (1 << i) == 0:\n",
    "                    r1 = find(v + (1 << i))\n",
    "                    merge(r0, r1)\n",
    "            # modify\n",
    "            for i in range(v.bit_length()):\n",
    "                if v & (1 << i):\n",
    "                    for j in range(v.bit_length()):\n",
    "                        if v & (1 << j) == 0:\n",
    "                            r1 = find(v - (1 << i) + (1 << j))\n",
    "                            merge(r0, r1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        def hash(x):\n",
    "            ans = 0\n",
    "            for c in x:\n",
    "                ans |= 1 << (ord(c) - ord('a'))\n",
    "            return ans\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x in vis or x not in cnt:\n",
    "                return 0\n",
    "            vis.add(x)\n",
    "            ans = cnt[x]\n",
    "            for i in range(26):\n",
    "                if x >> i & 1 == 0:\n",
    "                    ans += dfs(x | 1 << i) #add\n",
    "                else:\n",
    "                    ans += dfs(x ^ 1 << i) #delete\n",
    "                    for j in range(26): #replace\n",
    "                        if x >> j & 1 == 0:\n",
    "                            ans += dfs(x ^ (1 << i) | (1 << j))\n",
    "            return ans\n",
    "            \n",
    "        \n",
    "        vis = set()\n",
    "        cnt = Counter(map(hash, words))\n",
    "        #print(f'{cnt}')\n",
    "        mx, g = 0, 0\n",
    "        for k, _ in cnt.items():\n",
    "            n = dfs(k)\n",
    "            #print(f'k={k},n={n}')\n",
    "            mx = max(n, mx)\n",
    "            g += 1 if n > 0 else 0\n",
    "        return [g, mx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.data = [i for i in range(n)]\n",
    "        self.rank = [1] * n \n",
    "    def find(self, x):\n",
    "        if x == self.data[x]:\n",
    "            return x \n",
    "        else:\n",
    "            self.data[x] = self.find(self.data[x])\n",
    "            return self.data[x]\n",
    "    def un(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False \n",
    "        else:\n",
    "            self.data[fy] =fx\n",
    "            self.rank[fx] += self.rank[fy] \n",
    "            return True\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        arr = [0] * n \n",
    "        #print(n, len(set(words)))\n",
    "        for i, word in enumerate(words):\n",
    "            for c in word:\n",
    "                arr[i] |= 1 << (ord(c) - ord('a'))\n",
    "        \n",
    "        f = defaultdict(list)\n",
    "        dsu = DSU(n)\n",
    "        for i, x in enumerate(arr):\n",
    "            f[x].append(i)\n",
    "        \n",
    "        for idx, x in enumerate(arr):        \n",
    "            for i in range(26):\n",
    "                if (x >> i) & 1 == 0:\n",
    "                    nx = x | (1 << i)\n",
    "                    if nx in f:\n",
    "                        #for idx2 in f[nx]:\n",
    "                        dsu.un(idx, f[nx][0]) \n",
    "            for i in range(26):\n",
    "                if (x >> i) & 1 == 1:\n",
    "                    for j in range(26):\n",
    "                        if (x >> j) & 1 == 0:\n",
    "                            nx = (x | (1 << j)) ^ (1 << i)\n",
    "                            if nx in f:\n",
    "                                #for idx2 in f[nx]:\n",
    "                                dsu.un(idx, f[nx][0]) \n",
    "        for x, vec in f.items():\n",
    "            m = len(vec)\n",
    "            for i in range(1, m):\n",
    "                dsu.un(vec[i-1], vec[i])\n",
    "\n",
    "        ans = defaultdict(int) \n",
    "        for i in range(n):\n",
    "            fi = dsu.find(i) \n",
    "            ans[fi] = dsu.rank[fi]\n",
    "        res = [y for x, y in ans.items()]\n",
    "        return len(res), max(res) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.data = [i for i in range(n)]\n",
    "        self.rank = [1] * n \n",
    "    def find(self, x):\n",
    "        if x == self.data[x]:\n",
    "            return x \n",
    "        else:\n",
    "            self.data[x] = self.find(self.data[x])\n",
    "            return self.data[x]\n",
    "    def un(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False \n",
    "        else:\n",
    "            self.data[fy] =fx\n",
    "            self.rank[fx] += self.rank[fy] \n",
    "            return True\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        arr = [0] * n \n",
    "        #print(n, len(set(words)))\n",
    "        for i, word in enumerate(words):\n",
    "            for c in word:\n",
    "                arr[i] |= 1 << (ord(c) - ord('a'))\n",
    "        \n",
    "        f = defaultdict(list)\n",
    "        dsu = DSU(n)\n",
    "        for i, x in enumerate(arr):\n",
    "            f[x].append(i)\n",
    "        \n",
    "        for idx, x in enumerate(arr):        \n",
    "            for i in range(26):\n",
    "                if (x >> i) & 1 == 0:\n",
    "                    nx = x | (1 << i)\n",
    "                    if nx in f:\n",
    "                        #for idx2 in f[nx]:\n",
    "                        dsu.un(idx, f[nx][0]) \n",
    "            for i in range(26):\n",
    "                if (x >> i) & 1 == 1:\n",
    "                    for j in range(26):\n",
    "                        if (x >> j) & 1 == 0:\n",
    "                            nx = (x | (1 << j)) ^ (1 << i)\n",
    "                            if nx in f:\n",
    "                                #for idx2 in f[nx]:\n",
    "                                dsu.un(idx, f[nx][0]) \n",
    "        for x, vec in f.items():\n",
    "            m = len(vec)\n",
    "            for i in range(1, m):\n",
    "                dsu.un(vec[i-1], vec[i])\n",
    "\n",
    "        ans = defaultdict(int) \n",
    "        for i in range(n):\n",
    "            fi = dsu.find(i) \n",
    "            ans[fi] = dsu.rank[fi]\n",
    "        res = [y for x, y in ans.items()]\n",
    "        return len(res), max(res) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        def h(w):\n",
    "            ans = 0\n",
    "            for x in w:\n",
    "                ans |= (1 << (ord(x) - ord('a')))\n",
    "            return ans\n",
    "                \n",
    "        def dfs(i): \n",
    "            #print(f'w={w}')\n",
    "            if i not in mp or i in vis:\n",
    "                return 0\n",
    "            vis.add(i)\n",
    "            ans = mp[i]\n",
    "            #101 -> 110\n",
    "            for j in range(26):\n",
    "                if i >> j & 1:\n",
    "                    ans += dfs(i ^ (1 << j)) #del\n",
    "                    for k in range(26): #replace\n",
    "                        if i >> k & 1 == 0:\n",
    "                            ans += dfs(i ^ (1 << j) | (1 <<k))\n",
    "                else:\n",
    "                    ans += dfs(i | (1 << j)) #adding    \n",
    "            return ans\n",
    "                      \n",
    "       \n",
    "        mp = Counter()\n",
    "        for x in words:\n",
    "            mp[h(x)] += 1\n",
    "\n",
    "        n = len(words)\n",
    "        vis = set()\n",
    "        cnt, mx = 0, 0\n",
    "        #words.sort(key = lambda x: len(x))\n",
    "        #print(f'w={words},s={mp}')\n",
    "        for x in words:\n",
    "            t = dfs(h(x))\n",
    "            #print(f't={t}')\n",
    "            if t > 0:\n",
    "                cnt += 1\n",
    "            if t > mx:\n",
    "                mx = t\n",
    "        return [cnt, mx]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, words: List[str]) -> List[int]:\n",
    "        def pa(i):\n",
    "            nonlocal arr            \n",
    "            if arr[i][0] != i:\n",
    "                arr[i][0] = pa(arr[i][0])\n",
    "            return arr[i][0]\n",
    "        \n",
    "        def union(i, j):\n",
    "            nonlocal arr\n",
    "            arr[pa(j)][0] = pa(i)\n",
    "\n",
    "        n = len(words)\n",
    "        cache = defaultdict(list)\n",
    "        arr = [[i, 0] for i in range(n)]\n",
    "        bit = {ch: 1<<i for i, ch in enumerate(ascii_lowercase)}\n",
    "        for i, w in enumerate(words):\n",
    "            cur = reduce(operator.__or__, (bit[ch] for ch in w))\n",
    "            arr[i][1] = cur\n",
    "            cache[cur].append(i)\n",
    "\n",
    "        remove = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            tmp = cur = arr[i][1]            \n",
    "            for ch in ascii_lowercase:\n",
    "                for j in cache[bit[ch]^cur]:\n",
    "                    union(i, j)            \n",
    "            while tmp:\n",
    "                lowb = tmp & -tmp\n",
    "                remove[cur ^ lowb].append(i)\n",
    "                tmp ^= lowb\n",
    "        for row in remove.values():\n",
    "            for i in row[:-1]:\n",
    "                union(row[-1], i)\n",
    "        cnt = Counter(pa(i) for i in range(n))\n",
    "        # print(cache)\n",
    "        # print(arr)\n",
    "        # print(cnt)\n",
    "        return [len(cnt), max(cnt.values())]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
